class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if(n < 2)
            return 0;

        vector<int> dp(s.size());
        dp[1] = s[0]=='('&&s[1]==')' ? 2 : 0;
        int res = max(0, dp[1]);
        for(int i = 2; i < n; i++)
        {
            if(s[i] == ')')
            {
                if(s[i-1] == '(')
                {
                    dp[i] = dp[i-2] + 2;
                }
                else
                {
                    if(i-dp[i-1]-1>=0 && s[i-dp[i-1]-1] == '(')
                    {
                        dp[i] = dp[i-1] + 2;
                        if(i-dp[i-1]-1>0)
                            dp[i] += dp[i-dp[i-1]-2];
                    }
                }
            }
            res = max(res, dp[i]);
        }

        return res;
    }
};